package org.example.algorithm.heap;

public class MinHeap {
    //存储堆数据
    private int[] heap;
    //堆最大容量
    private int capacity;
    //堆当前大小
    private int size;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    //向堆中插入元素
    public void insert(int value) {
        if (size == capacity) {
            throw new IllegalStateException("heap is full");
        }
        heap[size] = value;
        size++;
        siftUp(size-1);
    }

    //删除堆顶元素（最小值）
    public int removeMin() {
        int temp = heap[0];
        heap[0] = heap[size-1];
        size--;
        siftDown(0);
        return temp;
    }

    //查看堆顶元素
    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("heap is empty");
        }
        return heap[0];
    }

    //上筛
    public void siftUp(int pos) {
        int parent = (pos - 1) / 2;
        if (parent >=0 && heap[pos] < heap[parent]) {
            swapHeap(pos, parent);
            siftUp(parent);
        }
    }

    //下筛
    public void siftDown(int pos) {
        int left = 2*pos+1;
        int right = 2*pos+2;
        int minPos = pos;
        if (left < size && heap[left] < heap[minPos]) {
            minPos = left;
        }
        if (right < size && heap[right] < heap[minPos]) {
            minPos = right;
        }
        if (minPos != pos) {
            swapHeap(pos, minPos);
            siftDown(minPos);
        }
    }

    //交换元素
    private void swapHeap(int from, int to) {
        int temp = heap[from];
        heap[from] = heap[to];
        heap[to] = temp;
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.insert(5);
        minHeap.insert(8);
        minHeap.insert(1);
        minHeap.insert(2);
        minHeap.insert(3);
        minHeap.insert(9);
        minHeap.insert(21);
        /**
        for (int i=0;i<minHeap.size;i++) {
            System.out.println(minHeap.heap[i]);
        }
         */
        int min = minHeap.peek();
        System.out.println(min);
        minHeap.removeMin();
        min = minHeap.peek();
        System.out.println(min);
        for (int i=0;i<minHeap.size;i++) {
            System.out.println(minHeap.heap[i]);
        }
    }

}
